package com.wc.AlgoOJ_train.train3_算法大礼包.c1_广度优先搜索.AG0204_素数路径;

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @Author congge
 * @Date 2024/1/25 23:10
 * @description http://43.138.190.70:8888/p/AG0204
 */
public class Main {
    static FastReader sc = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    static int N = 10010;
    static boolean[] isNotPrime = new boolean[N];
    static int[] primes = new int[N / 2];
    static int idx = 0;
    static int[] f = new int[N];
    static int[] base = new int[]{1, 10, 100, 1000};
    static int n, a, b;
    // 1000 ~ 10000中质数的个数
    static int num = 0;

    static void ola(int x) {
        isNotPrime[0] = isNotPrime[1] = true;
        for (int i = 2; i <= x; i++) {
            if (!isNotPrime[i])
                primes[++idx] = i;
            for (int j = 1; i * primes[j] <= x; j++) {
                isNotPrime[i * primes[j]] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }

    public static void main(String[] args) {
        ola(N - 1);

        for (int i = 1000; i < 10000; i++) {
            if (!isNotPrime[i]) {
                num++;
            }
        }
        n = sc.nextInt();

        while (n-- > 0) {
            a = sc.nextInt();
            b = sc.nextInt();
            Arrays.fill(f, 1000, N, 0);
            int res = bfs(a);
            if (res == -1) {
                out.println("Impossible");
            } else {
                out.println(res - 1);
            }
        }
        out.flush();
    }

    static int bfs(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        // 多走一步
        f[x] = 1;

        while (true) {
            if (q.isEmpty()) return -1;

            x = q.poll();
            if (f[x] > num + 1) {
                return -1;
            }
            if (x == b) {
                return f[x];
            }
            int baseX = x;

            // 变个位
            int bx = x - baseX % 10 * base[0];
            for (int i = 1; i <= 9; i += base[0]) {
                if (!isNotPrime[bx + i] && f[bx + i] == 0) {
                    f[bx + i] = f[x] + 1;
                    q.add(bx + i);
                }
            }
            baseX /= 10;
            // 变10位
            bx = x - baseX % 10 * base[1];
            for (int i = 0; i <= 90; i += base[1]) {
                if (!isNotPrime[bx + i] && f[bx + i] == 0) {
                    f[bx + i] = f[x] + 1;
                    q.add(bx + i);
                }
            }

            baseX /= 10;
            // 变百位
            bx = x - baseX % 10 * base[2];
            for (int i = 0; i <= 900; i += base[2]) {
                if (!isNotPrime[bx + i] && f[bx + i] == 0) {
                    f[bx + i] = f[x] + 1;
                    q.add(bx + i);
                }
            }
            baseX /= 10;
            // 变千位
            bx = x - baseX % 10 * base[3];
            for (int i = 1000; i <= 9000; i += base[3]) {
                if (!isNotPrime[bx + i] && f[bx + i] == 0) {
                    f[bx + i] = f[x] + 1;
                    q.add(bx + i);
                }
            }
        }
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    String nextLine() {
        String s = "";
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    // 是否由下一个
    boolean hasNext() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = br.readLine();
                if (line == null)
                    return false;
                st = new StringTokenizer(line);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }
}
